package A1动态规划;

public class LC_337打家劫舍3 {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){}
        TreeNode(int val){this.val=val;}
        TreeNode(int val,TreeNode left,TreeNode right){
            this.val=val;
            this.left=left;
            this.right=right;
        }
    }
    public static void main(String[] args){
        TreeNode root=new TreeNode(3);
        root.left=new TreeNode(2);
        root.left.right=new TreeNode(3);
        root.right=new TreeNode(3);
        root.right.right=new TreeNode(1);
        System.out.println(rob(root));
    }
    public static int rob(TreeNode root) {
        int[] result=robtree(root);
        return Math.max(result[0],result[1]);
    }
    public static int[] robtree(TreeNode cur){
        //0不偷，1偷
        int[] res=new int[2];
        if(cur==null)
            return res;
        int[] leftdp=robtree(cur.left);
        int[] rightdp=robtree(cur.right);
        res[1]=cur.val+leftdp[0]+rightdp[0];//偷当前结点
        //不偷当前节点
        res[0]=Math.max(leftdp[0],leftdp[1])+Math.max(rightdp[0],rightdp[1]);
        return res;
    }
}
